#include <iostream>
using namespace std;
/*
* 快速幂算法
时间复杂度O(logy);
y转化为二进制的位数：1+_[logy]
*/
void FastExponentiation() {
	int _x, _y;
	cout << "calculate pow(x,y):" << endl << "x = ";
	cin >> _x;
	cout << "y = ";
	cin >> _y;
	int result = 1;
	while (_y > 0) {
		if (_y & 1)
			result *= _x;
		_x *= _x;
		_y = _y >> 1;
	}
	cout << "pow(x,y) = " << result << endl;
}
/*
* 快速幂取模
(a * b) % m = [(a % m) * (b % m)] % m 
*/
void FastExponentiation_mod() {
	int _x, _y, _m;
	cout << "calculate pow(x,y) % mod:" << endl << "x = ";
	cin >> _x;
	cout << "y = ";
	cin >> _y;
	cout << "mod = ";
	cin >> _m;
	for (int i = 0; i < 1000; i++) {
		int x = _x, y = _y, m = _m;
		int result = 1;
		while (y > 0) {
			if (y & 1)
				result = (result * x) % m;
			x = (x * x) % m;
			y = y >> 1;
		}
		cout << "pow(x,y) % mod = " << result << endl;
	}
}
/*
* 慢速幂取模
*/
void SlowExponentiation_mod() {
	int _x, _y, _m;
	cout << "calculate pow(x,y) % mod:" << endl << "x = ";
	cin >> _x;
	cout << "y = ";
	cin >> _y;
	cout << "mod = ";
	cin >> _m;
	for (int j = 0; j < 1000; j++) {
		int x = _x, y = _y, m = _m;
		int result = 1;
		for (int i = 0; i < y; i++) {
			result *= x;
			result = result % m;
		}
		result = result % m;
		cout << "pow(x,y) % mod = " << result << endl;
	}
} 
/*
* 矩阵快速幂
*/
/*
* 递归快速幂
*/
int f(int m, int n) {   //m^n
	if (n == 1) return m;
	int temp = f(m, n / 2);
	return (n % 2 == 0 ? 1 : m) * temp * temp;
}
int main() {
	//FastExponentiation();
	long start, finish;
	start = clock();
	SlowExponentiation_mod();
	finish = clock();
	long r1 = finish - start;
	start = clock();
	FastExponentiation_mod();
	finish = clock();
	long r2 = finish - start;
	cout << (float)r1 / r2 << endl;
	return 0;
}
